package org.lql.algo.codecrush.hot100.substring;

import java.util.HashMap;
import java.util.Map;

/**
 * @author: liangqinglong
 * @date: 2025-10-22 14:35
 * @description: 560. 和为 K 的子数组 <a href="https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class SubarraySum {

	public int subarraySum(int[] nums, int k) {
		int[] preSum = new int[nums.length + 1];
		preSum[0] = 0;
		for (int i = 1; i <= nums.length; i++) {
			preSum[i] = nums[i - 1] + preSum[i - 1];
		}
		int count = 0;
		Map<Integer, Integer> map = new HashMap<>();
		for (int item : preSum) {
			int target = item - k;
			if (map.containsKey(target)) {
				count += map.get(target);
			}
			map.put(item, map.getOrDefault(item, 0) + 1);
		}
		return count;
	}

	public static void main(String[] args) {
		SubarraySum subarraySum = new SubarraySum();
		// 2
		System.out.println(subarraySum.subarraySum(new int[]{1, 1, 1}, 2));
		// 2
		System.out.println(subarraySum.subarraySum(new int[]{1, 2, 3}, 3));
		// 3
		System.out.println(subarraySum.subarraySum(new int[]{1, -1, 0}, 0));
	}
}
